package leetcode.linklist;

/*
 2. 两数相加

 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

 示例：
 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 输出：7 -> 0 -> 8
 原因：342 + 465 = 807
*/

import java.util.ArrayList;
import java.util.List;

public class AddTwoNumbers2 {

    /**
     * Definition for singly-linked list.
     */
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static void main(String[] args) {
//        ListNode l1 = initList(new int[]{2,4,3});
//        ListNode l2 = initList(new int[]{5,6,4});

        ListNode l1 = initList(new int[]{9,9,9,9,9,9,9});
        ListNode l2 = initList(new int[]{9,9,9,9});

        ListNode r = test(l1, l2);

        printList(l1);
        printList(l2);
        printList(r);
    }

    private static ListNode test(ListNode l1, ListNode l2) {
        if(null != l1 && null == l2)
            return l1;
        else if(null == l1 && null != l2)
            return l2;
        else if(null == l1 && null == l2)
            return null;

        int base = 10;      // x进制
        int carry = 0;      // 进位标识
        int t = 0;          // 临时变量
        int l1Val;
        int l2Val;

        // 链表指针
        ListNode result = null; // 最后返回的结果
        ListNode pos = null;
        ListNode next = null;

        // 初始状态标识
        boolean startupStatus = true;

        while(null != l1 || null != l2) {
            l1Val = 0;
            l2Val = 0;

            if(l1 != null) {
                l1Val = l1.val;
            }

            if(l2 != null) {
                l2Val = l2.val;
            }

            t = l1Val + l2Val + carry;

            if(t >= base)
                carry = 1;
            else
                carry = 0;

            next = new ListNode(t%base);

            if(startupStatus) {
                pos = next;
                result = next;
                startupStatus = false;
            } else {
                pos.next = next;
                pos = pos.next;
            }

            l1 = null != l1 ? l1.next : null;
            l2 = null != l2 ? l2.next : null;
        }

        if(1 == carry) {
           pos.next = new ListNode(carry);
        }

        return result;
    }

    public static ListNode initList(int[] nums) {
        if(null == nums || nums.length == 0)
            return null;

        ListNode head = null;
        ListNode pos = null;
        ListNode next = null;
        for(int i = 0; i < nums.length; i++) {
            next = new ListNode(nums[i]);
            if(0 == i) {
                pos = next;
                head = pos;
            } else {
                pos.next = next;
                pos = pos.next;
            }
        }

        return head;
    }

    public static void printList(ListNode l) {
        if(null == l)
            return;

        List list = new ArrayList();
        while(null != l) {
            list.add(l.val);
            l = l.next;
        }

        System.out.println(list.toString());
    }
}
